/*
冒泡排序：
        相邻的两个元素依次进行比较，每一轮将会实现将最值放在最后，最多经过n-1轮就会将数据排好序

*/
#include <stdio.h>
//冒泡排序
void BubbleSort(int NUM[],int n)
{
    int i,j,t;
    for(i=0;i<n-1;i++)//最多需要多少轮
    {
        for(j=0;j<n-1-i;j++)//交换的次数j
        {
            if(NUM[j]>NUM[j+1])
            {
                //交换
                t=NUM[j];
                NUM[j]=NUM[j+1];
                NUM[j+1]=t;
            }
        }
    }
}
//选择排序
void SelectSort(int num[],int n)
{
    int i=0,j,t,min;
    //从无序区找到最小值的下标 与无序区起始位置去进行交换
    for(i=0;i<n-1;i++)
    {
        min=i;//min 最小值的下标/有序区下一个位置
        for(j=i+1;j<n;j++)
        {
            if(num[j]<num[min])//如果当前无序区中的元素比当前最小的数据还要小 保存当前最小下标
            {
                min = j;
            }
        }
        //经过一轮以后 找到当前最小值的下标
        t=num[i];
        num[i]=num[min];
        num[min]=t;
    }
}
//插入排序  拿未排序的元素 在已排序元素中，从后往前比较，只要比已排序的元素小就进行交换
void InsertSort(int num[],int n)
{
    int i,j,t;
    i=0;//i是已排序的最后一个下标
    for(i=0;i<n-1;i++)
    {
        //在未排序从i+1个位置到下标0进行比较
        for(j=i+1;j>=0;j--)
        {
            //如果当前未排序元素值比已排序元素小就进行交换
            if(num[j]<num[j-1])
            {
                //交换
                t=num[j];
                num[j]=num[j-1];
                num[j-1]=t;
            }
            else{
                break;
            }
        }
    }
}
//快速排序 挖坑法
void QuickSort(int *a,int begin,int end)
{
    int i=begin;//第一位
    int j=end;//最后一位
    int key=a[i];//将第一位作为基准值

    //进行排序   左边都比基准值小，右边比基准值大
    while(i<j)
    {
        //如果右边的值比基准值大，就赋值否则继续向前移动
        while(i<j&&a[j]>=key)//i<j 是当前while循环的结束条件 如果没有这个出现越界
        {
            j--;//继续走
        };//如果不成立，也就是a[j]<key;右面的比key小，那就换位置
        //把a[j]的数据给a[i]
        a[i]=a[j];

        //将事先保存好的基准值与左边的值进行比较，如果基准值大，保持不变，i往前
        //然后 判断一下这个新的a[i]，也就是之前的a[j]跟key值的关系---> 一定是 a[i]<key
        //所以把i向前移动一下，i++
        while(i<j&&a[i]<=key)
        {
            i++;
        }
        //移动完以后，把新的位置的a[i]的数值 给刚才的 a[j],然后开始下一次循环
        a[j]=a[i];
    }

    //跳出循环，将基准值放入数据a[i]中
    a[i] = key;
    //对基准值左边 的所有数据 再次进行快速查找（递归）
    if (i-1 > begin) 
    {
        QuickSort(a, begin, i-1);
    }
 
    //对基准值右边的所有数据再次进行快速查找（递归）
    if (i+1 < end)
    {
        QuickSort(a, i+1, end);

    }
}
void print_arr(int NUM[],int n)
{
    for(int i=0;i<n;i++)
    {
        printf("%d\t",NUM[i]);
    }
    printf("\n");
}
int main(void)
{
    int num[10]={23,21,45,6,345,2456,42,56,3,3457};
    //BubbleSort(num,10);//冒泡排序
    //SelectSort(num,10);//选择排序
    //InsertSort(num,10);//插入排序
    QuickSort(num,0,9);//快速排序
    print_arr(num,10);
}